//问题描述
/*
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
*/

//深度优先递归解法
class Solution {
public:
    int maxDepth(TreeNode* root) {
		//空节点高度为0
        if(root == nullptr) return 0;
		//否则就是左右子树的高度的较大值+1
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};

// 层次遍历解法
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        int res = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            size_t size = que.size();
			// 只有每一层的节点全部处理完才进行层数叠加操作
             while(size--){
                TreeNode *cur = que.front();
                que.pop();
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            res++;
        }
        return res;
    }
};

/*
给定一个N叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
*/
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
//深度优先——递归写法
class Solution {
public:
    int maxDepth(Node* root) {
        if(root == nullptr) return 0;
        // 根不为空 初始化深度为1
        int deep = 0;
        for(auto c:root->children){
		//注意这里不要使用deep = maxDepth(c) > deep? maxDepth(c):deep;
		// 因为这样会导致递归次数多了一倍，造成很大的时间资源浪费
            int d = maxDepth(c);
            deep = d > deep? d:deep;
        }
        return deep+1;
    }
};

//广度优先处理——层次遍历求深度
// 基本上是模仿二叉树的遍历实现的，只是在下面的103行处理有特点
class Solution {
public:
    int maxDepth(Node* root) {
        if(root == nullptr) return 0;
        // 初始化层次遍历辅助队列
        queue<Node*> que;
        // 根节点入队
        que.push(root);
        // 预设深度depth为0，因为节点是在出队的时候处理
        int depth = 0;
        // 队列不为空则说明未处理完
        while(!que.empty()){
            // q_size是当前节点所在的层的节点数，确保按层进行处理
            size_t q_size = que.size();
            Node* node ;
            while(q_size--){
                node = que.front();
                que.pop();
                // 当前处理的节点的子结点个数，这也是与二叉树的区别
                int n_size = node->children.size();
                for(int i=0;i<n_size;i++){
                    que.push(node->children[i]);
                }
            } 
            // 处理完一层，深度加一
            depth++;
        }
    return depth;
    }
};